MacHack 1998/MacHack 1998.toast/Programming Contest/!Problems

Text File | 1998-06-20 | 17.2 KB | 445 lines | [TEXT/R*ch]

Problem 01 - Mode Sort

This problem is to sort an input string of N characters, N<1000000, based on
the number of times a character occurs in the input.  The most frequently
occurring character should be sorted to the front of the string, followed by
the next most frequently occurring character, etc.  For characters occurring
the same number of times, the character that occurs first in the input should
be sorted to the front.

Header specification

pascal OSErr ModeSort( const FSSpec* infile, const FSSpec* outfile );

Input specification

The infile input file contains the characters.  Input characters other than
those printable low ascii characters c, 0x20<c<0x7f, must be ignored.

Output specification

The outfile must be created and then filled with the sorted characters.  It's
final length should be exactly the same as the count of characters in the
allowed range (0x20<c<0x7f) (which may be shorter than the infile file length).

Sample input

abcdefghabbcccdddeee
or
012345678911234567892123456789312345678941234567895123456789612345678971234567891

Sample output

ccccddddeeeebbbaafgh
or
111111111122222222233333333344444444455555555566666666677777777788888888999999990

Problem 02 - Hower of Tanoi

This problem is to solve a variant of the Tower of Hanoi puzzle.  You remember
the Tower of Hanoi, a board with three pegs, one of which has N disks of size
1, 2, 3, ... N, with the smallest disk at the top.  In the standard puzzle, the
goal is to move all of the disks from one peg to another peg, by repeatedly
moving a disk from the top of one peg to another peg without ever placing a
larger disk on top of a smaller disk.

In our Hower of Tanoi problem, the objective and the constraints are the same,
except that the disks on the first peg are initially in random order. You can
still only move a smaller disk onto a larger disk.

Your objective is output the moves required to place all the disks on peg 3 in
order with the smallest disk at the top.

Input specification

The first line of the input file contains an integer M, M<1000, the number of
disks in the problem.  The next M lines contain the numbers 1 .. M, one number
per line, randomly ordered, where the first number is the size of the top disk
on peg 1, the second number is the size of the 2nd disk from the top, etc.

Output specification

The output is a sequence of lines, each representing a single move,  consisting
of the source peg number followed by a comma (',') followed by the destination
peg number, followed by a return character.

Sample input

2
2
1

Sample output

1,3
1,3

Problem 03 - Perimeter

You are in charge of protecting a set of defenseless homeowners from predators
that roam the area by constructing a single fence of minimum length that
encloses all of the homes.

The prototype for your solution is as follows:

typedef struct Node {
    long xCoord;
    long yCoord;
} Node;

void Perimiter(
    long numHomes,
    Node homesToEnclose[],
    long *numNodesInPerimiter,
    long nodesInPerimiter[]
);

You are given a list homesToEnclose of numHomes homes to protect  (numbered 0
to numHomes-1) by constructing a fence around the homes. You should return a
list nodesInPerimiter of the numNodesInPerimiter homes to be connected by a
fence.  The fence must enclose all of the homes using the minimum amount of
fencing material.



Problem 04 - Text Processing

const
    kMaxHandleSize = 1000000;
const
    kActionMove = 1;
    kActionInsert = 2;
    kActionDelete = 3;
    kActionSearch = 4;
    kActionSearchAndReplace = 5;
const
    kFlagCaseSensitiveBit = 0;
    kFlagGlobalBit = 1;
    kFlagBackwardsBit = 2;
type
  ActionRecord = record
    action: UInt32;
    amount: SInt32;
    flags: UInt32;
    search: Str255;
    replace: Str255;
  end;
  ActionRecordArray = array[0..0] of ActionRecord;
  ActionRecordArrayPtr = ^ActionRecordArray;

procedure TextProcess( data: Handle; action_count: UInt32; actions:
ActionRecordArrayPtr );

Given an unlocked handle to a block of text, you need to apply a sequence of
actions to the data.  You will be required to insert text, delete text, search
for text, search for and replace text.  All required actions take place at the
position of the current selection pointer, which starts at zero, before the
first character in the data.  In response to each of the action commands you
need to perform the following:

kActionMove - move the internal position forward by the amount field (which may
be negative).  (Example, kActionMove with amount set to kMaxHandleSize will set
the internal pointer to be GetHandleSize( data )).

kActionInsert - Insert the replace string at the current location.  (Example,
if the internal pointer is GetHandleSize( data ), then the replace string will
be appended to the handle.

kActionDelete - Delete the number of characters specified by the amount field.
The internal position pointer is never moved.  If the amount field is greater
than the number of characters after the internal pointer, then fewer characters
are deleted such that the handle is truncated at the current value of the
selection pointer.

kActionSearch - search forward (backwards if the kFlagBackwardsBit is set in
the flags field) for the search field (case sensitively if the
kFlagCaseSenstitiveBit is set in the flags field).  The position pointer should
be set to point before the first character of the string if it is found, or at
GetHandleSize (zero if backwards) if not found.  If there is a match at the
initial position, it is not counted (ie, kActionMove -kMaxHandleSize, kSearch
'hello', kSearch 'hello' finds the second occurance of 'hello').

kActionSearchAndReplace - search forward (or backward if the kFlagBackwardsBit
is set in the flags field), but when a match is found, replace it with the
replace string, leaving the position pointer unmoved.  If the kFlagGlobalBit is
set in the flags field, continue searching as long matches continues to be
found.  Repeated searches begin after the previous replace string (i.e., never
replace any characters of the replace string).  For example, if you replace
'aaa' with 'ABA' (case insensitively) in 'aaaaaaaa' you will get 'ABAABAaa',
not 'ABABABAa'.  Replace never moves the internal position pointer.

The internal selection pointer is constrained to be in the range of 0 and
GetHandleSize(data), inclusive, at all times.  Should any action cause the
selection pointer to become less than zero (or greater than GetHandleSize),
then you must reset it to zero (or GetHandleSize, respectively).  The handle
size will never exceed 1 Meg, and you will have plenty of memory to play with.

Characters from chr(127)-chr(255) will never appear in the handle or any
strings.



Problem 05 - Database

type
    StringsHandle = Handle; // Sequence of Pascal Strings packed together
    DatabaseHandle = Handle; // Must be a real handle

procedure DatabaseInit( var database: Handle; field_count: UInt32 );
procedure DatabaseAddEntry( database: Handle; entry: StringsHandle );
procedure DatabaseFindEntry( database: Handle; field: UInt32; const match:
Str255; var entry: StringsHandle );
procedure DatabaseDeleteEntry( database: Handle; field: UInt32; const match:
Str255 );
function DatabaseCount( database: Handle ): UInt32;
procedure DatabaseGetIndEntry( database: Handle; index: UInt32; var entry:
StringsHandle );

Your task is to write a set of routines to maintain a database.

DatabaseInit creates a new, empty database ready to accept records with
field_count string fields.  The database is stored in the database Handle.

DatabaseAddEntry adds an entry (which is a Handle to field_count pascal strings
packed together conceptually numbered 1 to field_count)

DatabaseFindEntry finds an entry whose field (between 1 and field_count) string
is exactly equal to match.  The entry is returned in a newly created handle
(which will be disposed of using DisposeHandle).  Return nil if no match is
found.  If more than one entry matches, you must return the earliest added
entry.

DatabaseDeleteEntry finds the entry that DatabaseFindEntry would find, and if
found removes it from the database.

DatabaseCount returns the number of entries in the database.

DatabaseGetIndEntry returns the entries in the Database in the order they were
entered, 1 for the earliest entered, DatabaseCount the last entered.

All the database information must be stored in the real Mac memory manager
handle - it will be disposed with DisposeHandle and that must release all
memory, so do not store any extra information outside the handle.  Also, you
must be able to deal with having multiple databases instantiated
simultaneously.

You will not be given invalid parameters so you don't need to handle error
checking, and there will be plenty of memory.

All strings are case sensitive (ie, treated as eight bit binary data).


Problem 06 - Legal Chess Moves

Deep Thought has beaten mankind as the game once thought to exemplify human
intuition.  Our MacHack laboratory is secretly constructing an implant that
will neutralize the calculation advantage held by the computer, and restore
mankind to its rightful place as the champion of chess, through intuition and
cunning.  Your job is to write the code that will calculate the board position
resulting from a sequence of moves, along with the legal moves available to the
next player.  With this advantage, the human chess master will be able to
concentrate on strategy, rather than waste time calculating moves.

The prototype for your solution is as follows:

typedef enum {kEmpty=0,kWhite,kBlack} PieceColor;
typedef enum {kNone=0,kPawn,kKnight,kBishop,kRook,kQueen,kKing} PieceRank;

typedef struct Square {
    UInt16 row;    // 0..7, white initially occupies rows 0 and 1, black 7 and 6
    UInt16 col;    // 0..7, white king starts at (row,col) == (0,4)
} Square;

typedef struct ChessMove {
    Square fromSquare;
    Square toSquare;
    Boolean capture;
    Square capturedSquare;    // valid only if capture==TRUE
} ChessMove;

typedef struct ChessPiece {
    PieceColor whichColor;
    PieceRank whichRank;
    Square pieceLocation;
} ChessPiece;

pascal void FindLegalChessMoves(
    UInt32 numPriorMoves,
    ChessMove priorMoves[],
    UInt32 *numPiecesRemaining,
    ChessPiece piecesRemaining[],
    UInt32 *numLegalMoves,
    ChessMove legalMoves[]
);

Your FindLegalChessMoves routine will be called with a list (priorMoves) of
numPriorMoves that have already taken place from the normal initial chessboard.
You should model the effects of those moves and generate a list
(piecesRemaining) of the numPiecesRemaining pieces remaining, including their
location on the board, and a list (legalMoves) of all numLegalMoves legal moves
available to the next player.  You should follow all rules of Chess with two
exceptions: stalemates can be ignored, and pawns always become Queens when
promoted.  Remember to include castling moves when appropriate (indicated by
moving the king the appropriate two/three squares) and en passant pawn
captures.


Problem 07 - Graph

procedure GraphInit( var graph: Handle; verrticies: UInt32 );
procedure GraphAddDirectedEdge( graph: Handle; vertex1, vertex2: UInt32 );
procedure GraphFindRoute( graph: Handle; vertex1, vertex2: UInt32; var
verticies: Handle );

Your task is to write a set of routines to create and traverse a directed
graph.

GraphInit creates a new, empty directed graph ready to accept directed edges
with verrticies verticies.

GraphAddDirectedEdge adds a directed edge from vertex1 to vertex2

GraphFindRoute find a route from vertex1 to vertex2.  If such a route exists,
then verticies is returns as a real Mac handle to an array of UInt32s, the
first is vertex1, the last is vertex2.  Each successive vertex must have
previously had an edge added with GraphAddDirectedEdge.  If no route exists,
return nil for verticies.  No vertex should appear more than once in the
verticies handle, except for the case where vertex1 is the same as vertex2, in
which case you must find a circular route from vertex1 back to itself and so
vertex1 will appear exactly twice, once at the start and once at the end of the
verticies handle.

All the graph information must be stored in the real Mac memory manager handle
- it will be disposed with DisposeHandle and that must release all memory, so
dont store any extra information outside the handle.  Also, you must be able to
deal with having multiple graphs instantiated simultaneously.


Problem 08 - Packing

PointArray = array[0..0] of Point;
PointArrayPtr = ^PointArray;

procedure PackBoxes( frame: Rect; box_count: UInt32; boxes: PointArray;
toplefts: PointArrayPtr );

Your task is to pack a set of 2-dimensional boxes into a given frame rectangle
such that the interior of the boxes do not intersect.

The box dimensions are represented by height (the .v component) and width (the
.h component) in the boxes array.  You must find a way to fit all the
rectangles inside the frame without overlapping.  Just like QuickDraw standard
rectangles, two adjacent rectangles could have the same right/left coordinate,
so that they are touching but not overlapping.  Similarly, rectangles may touch
the edge of the frame.  When you find a solution, you should return the topleft
coordinates of each rectange.  Rectangles may only be moved horrizontally or
vertically, they may not be rotated.

Example

frame = (10, 10, 100, 100 )
box_count = 3
boxes = { (50, 90), (40, 40), (40, 50) }

return

toplefts = { (10, 10), (60, 10), (60, 50) }



Problem 09 - State Machine

type GetNextCharProc = function( curstate: UInt32 ): UInt32;

procedure StateMachineInit( var state_machine: Handle; states: UInt32; chars:
UInt32 );
procedure AddTransition( state_machine: Handle; state1, state2: UInt32;
first_char, last_char: UInt32 );
procedure RunStateMachine( state_machine: Handle; start_state: UInt32;
GetNextChar: GetNextCharProc; var stop_state: UInt32 );

This problem requires you to maintain and operate a state machine, consisting
of rules that change the current machine state based on the current input.  Our
state machines do not require that you produce any output other than the
machine state.

StateMachineInit creates a new, empty state machine ready to accept state
transitions, and containing states states (numbers 1 to states) and chars
characters (numbered 1 to chars).  All the state machine information must be
stored in the real Mac memory manager handle - it will be disposed with
DisposeHandle and that must release all memory, so dont store any extra
information outside the handle.  Also, you must be able to deal with having
multiple state machine instantiated simultaneously.

AddTransition adds a transition from state1 to state2 for characters between
(inclusive) first_char and last_char.  When you get to state1 and get a
character between first_char and last_char you should proceed to state2.  The
new transition overrides and previous transitions for these characters from
state1 (ie, if you get transition 1->2 for chars 1-10, and then 1->3 for chars
5-6, you now have transition 1->2 for chars 1-4 and 7-10 and transition 1->3
for chars 5-6).

RunStateMachine starts in start_state and calls GetNextChar repeatedly until
either it returns 0 or until it returns a character for which there is no
transition at the current state.  Each time GerNewChar supplies a character,
the current state is updated based on the transition rule that applies to that
combination of current state and current input.  When GetNextChar supplies a
state for which no transition rule exists, the state machine halts and the
final state is returned in stop_state.

Problem 10 - Interpreter

Write an interpreter for this simple 32-bit integer language with 26 registers
labeled A-Z.

type RegisterArray = array[0..25] of SInt32;

procedure Interpret( source: Handle; var result: RegisterArray );

source consists of a number of lines of the form:

[<label>:][<tab><instruction><tab><operand-list>]<cr>

<label> is a sequence of at least two alphanumerics (0-9a-zA-Z_)
(casesensitive).
<operand-list> is a sequence of operators seperated by commas
other than the tabs and crs, no white space is allowed.

<instruction> (and appropriate operands are:

MOVE    <value>,<register>            (set <register> to <value>)
ADD     <value1>,<value2>,<register>  (set <register> to <value1>+<value2>)
SUB     <value1>,<value2>,<register>  (set <register> to <value1>-<value2>)
JMP     <label>                       (jump to line labeled with <label>)
JEQ     <value1>,<value2>,<label>     (jump to <label> if <value1> = <value2>)
JLE     <value1>,<value2>,<label>     (jump to <label> if <value1> <= <value2>)
JSR     <label>                       (jump to subroutine at <label>)
RTS                                   (return from subroutine)
PUSH    <value>                       (push value on to stack)
POP     <register>                    (pop value from stack)

<register> is a single uppercase letter in the range A..Z
<number> is an optional minus sign followed by decimal digits
<value> is a <register> or a <number>

Note that the data stack and subroutine stack are independent stacks.  A RTS is
used to stop the program (that is, consider that you have JSRed to the initial
line of the source handle).  For example:

    PUSH    10
    JSR    setA
    JSE setB
    RTS
setA:
    POP    A
    RTS
setB:    MOVE    A,B
    RTS

Interpret takes the source handle and JSRs to it, presetting the registers
according to the register array.  When the code returns, the register array is
set to the final value of all the registers.  Both subroutine and data stacks
should be large (at least 1000 entries each).

ENDENDEND